<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        var quickSort = function (nums) {
            if (nums.length <= 1) {
                return nums;
            }
            let pivotIndex = parseInt(nums.length / 2);
            let pivot = nums.splice(pivotIndex, 1)[0];

            let left = [],
                right = [];

            for (let i = 0; i < nums.length; i++) {
                if (nums[i] < pivot) {
                    left.push(nums[i]);
                } else {
                    right.push(nums[i]);
                }
            }

            return quickSort(left).concat([pivot], quickSort(right));
        }

        // 哨兵
        // var devide = function (nums, left, right) {
        //     if (left >= right) {
        //         return nums;
        //     }

        //     let baseIndex = parseInt((left + right) / 2);
        //     let i = left,
        //         j = right;

        //     while (i <= j) {
        //         while (nums[i] < nums[baseIndex]) {
        //             i++;
        //         }
        //         while (nums[j] > nums[baseKIndex]) {
        //             j--;
        //         }

        //         if (i <= j) {
        //             let temp = nums[i];
        //             nums[i] = nums[j];
        //             nums[j] = temp;
        //         }

        //         return i;
        //     }
        // }

        // var quickSort = function (nums, left = 0, right = nums.length - 1) {
        //     // let left = 0,right = nums.length - 1;
        //     if (nums.length <= 1) {
        //         return nums;
        //     }

        //     var index = devide(nums, left, right);

        //     if (left < index - 1) {
        //         quickSort(nums, left = 0, right = index - 1);
        //     }
        //     if (end > index) {
        //         quickSort(nums, left = index, right = nums.length - 1);
        //     }
        // }

        console.log(quickSort([2, 0, 2, 1, 1, 0]));
    </script>
</body>

</html>